A deterministic finite automaton (DFA) or deterministic finite state machine is a set of states tied together by a set of transitions. The transitions may specify movement from one state to another based on some input. A DFA at a given state and for a given input has only one transition to a next state. Examples of such deterministic finite automaton may be designed in hardware or software to produce results based on the state and any input. Some applications for a DFA involve electronic systems, such as network equipment and computer operated systems.
A DFA may be constructed from a non-deterministic finite automaton (NFA), which may be constructed from a regular expression. Construction of a DFA can be expensive in terms of time and computing resources. For longer expressions, construction of a DFA can take extended periods of time and require all resources of a machine, thereby affecting performance of the machine.
There is a need in the art for improved methods of constructing DFAs which won't tie up an undesirable amount of computer time and computing resources.